﻿// 小q的数列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
链接：https://ac.nowcoder.com/acm/contest/21763/B
来源：牛客网

小q最近迷上了各种好玩的数列，这天，他发现了一个有趣的数列，其递推公式如下：
​

现在，他想考考你，问：给你一个n，代表数列的第n 项，你能不能马上说出f(n) 的值是多少，以及f(n) 所代表的值第一次出现在数列的哪一项中？
（即，若这个数列里某几项
𝑓(𝑛1)=𝑓(𝑛2)=~~=𝑓(𝑛𝑘) 的值是相等的，则输出最小的那个n 的值
min(n1,n2,~~,nk) ）。

在本题中，⌊x⌋表示向下取整，xmody 表示x 除以y 的余数。
输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数
T(1≦T≦5×10^5) 代表数据组数，每组测试数据描述如下：
在一行上输入一个整数n(1≦n≦10^18 ) ，代表数列的第n 项。
输出描述:
对于每一组测试数据，在单独的一行上输出两个整数，分别代表f(n) 的值和f(n) 所代表的值第一次出现在数列的哪一项中。


示例1
输入
复制
6
0
1
2
3
4
5
输出
复制
0 0
1 1
1 1
2 3
1 1
2 3
说明
这个数列的前六项为：
f(0)=0 ；
f(1)=1 ；
f(2)=f(⌊2,2⌋)+f(2mod2)=f(1)+f(0)=1+0=1 ；
f(3)=f(⌊2,3⌋)+f(3mod2)=f(1)+f(1)=1+1=2 ；
f(4)=f(⌊2,4⌋)+f(4mod2)=f(2)+f(0)=1+0=1 ；
f(5)=f(⌊2,5⌋)+f(5mod2)=f(2)+f(1)=1+1=2 。


*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 